// https://leetcode.cn/problems/clone-graph/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用深度优先搜索递归克隆图结构
// 2. 使用数组记录已克隆节点，避免重复创建和循环引用
// 3. 对于每个节点，创建新节点并递归克隆所有邻居
// 4. 遇到已访问节点直接连接，确保图的连通性
// 5. 时间复杂度：O(N)，空间复杂度：O(N)

// 本题辅助函数由AI生成

#include <iostream>
using namespace std;

#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>

class Node 
{
public:
    int val;
    vector<Node*> neighbors;
    Node() 
    {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) 
    {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) 
    {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution 
{
private:
    Node* dfs(Node* node, Node** vis)
    {
        if (node == nullptr) return nullptr;
        
        Node* root = new Node(node->val);
        vis[node->val] = root;

        int size = node->neighbors.size();
        for (int i = 0 ; i < size ; i++)
        {
            if (vis[node->neighbors[i]->val] == nullptr)
            {
                root->neighbors.push_back(dfs(node->neighbors[i], vis));
            }
            else 
            {
                root->neighbors.push_back(vis[node->neighbors[i]->val]);
            }
        }

        return root;
    }
public:
    Node* cloneGraph(Node* node) 
    {
        if (node == nullptr) return nullptr;
        Node* vis[101] = {nullptr};
        return dfs(node, vis);
    }
};

// 创建测试图：[[2,4],[1,3],[2,4],[1,3]]
Node* createTestGraph1() 
{
    /*
        构建如下图：
        1 -- 2
        |    |
        4 -- 3
    */
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    
    node1->neighbors = {node2, node4};
    node2->neighbors = {node1, node3};
    node3->neighbors = {node2, node4};
    node4->neighbors = {node1, node3};
    
    return node1;
}

// 创建测试图：单节点
Node* createTestGraph2() 
{
    return new Node(1);
}

// 创建测试图：空图
Node* createTestGraph3() 
{
    return nullptr;
}

// 检查两个图是否相同（通过值比较）
bool areGraphsEqual(Node* node1, Node* node2) 
{
    if (node1 == nullptr && node2 == nullptr) return true;
    if (node1 == nullptr || node2 == nullptr) return false;
    if (node1->val != node2->val) return false;
    if (node1->neighbors.size() != node2->neighbors.size()) return false;
    
    // 简单比较邻居值（实际应该比较整个图结构，这里简化）
    for (size_t i = 0; i < node1->neighbors.size(); i++) 
    {
        if (node1->neighbors[i]->val != node2->neighbors[i]->val) 
        {
            return false;
        }
    }
    return true;
}

// 打印图结构（BFS方式）
void printGraph(Node* node) 
{
    if (node == nullptr) 
    {
        cout << "空图" << endl;
        return;
    }
    
    vector<Node*> visited(101, nullptr);
    vector<Node*> queue;
    queue.push_back(node);
    visited[node->val] = node;
    
    cout << "图结构: " << endl;
    while (!queue.empty()) 
    {
        Node* curr = queue.front();
        queue.erase(queue.begin());
        
        cout << "节点 " << curr->val << " 的邻居: ";
        for (Node* neighbor : curr->neighbors) 
        {
            cout << neighbor->val << " ";
            if (visited[neighbor->val] == nullptr) 
            {
                visited[neighbor->val] = neighbor;
                queue.push_back(neighbor);
            }
        }
        cout << endl;
    }
}

// 释放图内存
void deleteGraph(Node* node) 
{
    if (node == nullptr) return;
    
    unordered_set<Node*> visited;
    queue<Node*> q;  
    q.push(node);
    visited.insert(node);
    
    while (!q.empty()) 
    {
        Node* curr = q.front();
        q.pop(); 
        
        for (Node* neighbor : curr->neighbors) 
        {
            if (visited.find(neighbor) == visited.end()) 
            {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
        delete curr;
    }
}

int main() 
{
    Solution solution;
    
    cout << "=== 测试用例1: 完整图 ===" << endl;
    Node* original1 = createTestGraph1();
    cout << "原图:" << endl;
    printGraph(original1);
    
    Node* cloned1 = solution.cloneGraph(original1);
    cout << "克隆图:" << endl;
    printGraph(cloned1);
    
    cout << "克隆是否成功: " << (areGraphsEqual(original1, cloned1) ? "是" : "否") << endl;
    cout << "是否是深拷贝: " << (original1 != cloned1 ? "是" : "否") << endl;
    
    cout << "\n=== 测试用例2: 单节点 ===" << endl;
    Node* original2 = createTestGraph2();
    Node* cloned2 = solution.cloneGraph(original2);
    cout << "单节点克隆: " << (cloned2 != nullptr ? "成功" : "失败") << endl;
    cout << "节点值: " << (cloned2 != nullptr ? cloned2->val : -1) << endl;
    
    cout << "\n=== 测试用例3: 空图 ===" << endl;
    Node* original3 = createTestGraph3();
    Node* cloned3 = solution.cloneGraph(original3);
    cout << "空图克隆: " << (cloned3 == nullptr ? "成功" : "失败") << endl;
    
    // 释放内存
    deleteGraph(original1);
    deleteGraph(cloned1);
    deleteGraph(original2);
    deleteGraph(cloned2);
    delete original3; 
    
    cout << "\n=== 所有测试完成 ===" << endl;
    
    return 0;
}